/**
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
*/
class Solution {
    List<String> res=new ArrayList();
    public List<String> letterCombinations(String digits) {
    Map<Character,String> map=new HashMap();
    map.put('2',"abc");
    map.put('3',"def");
    map.put('4',"ghi");
    map.put('5',"jkl");
    map.put('6',"mno");
    map.put('7',"pqrs");
    map.put('8',"tuv");
    map.put('9',"wxyz");

    if(digits.length()==0) return res;
    dfs(new StringBuilder(),digits,map,0);
    return res;
    }
    public void dfs(StringBuilder sb,String digits,Map<Character,String> map,int n){
        if(n==digits.length()){
            res.add(sb.toString());
            return; 
        }

            char num=digits.charAt(n);
            System.out.println(num);
            String nums= map.get(num);
            int len=nums.length();
            for(int j=0;j<len;j++){
                sb.append(nums.charAt(j));
                dfs(sb,digits,map,n+1);
                sb.deleteCharAt(n);
            }
            
    }
}